1. Technical Field
This invention is directed toward a system and method for compressing digital pen stroke data. More specifically, the invention is directed toward a system and method for compressing digital pen stroke data utilizing curve simplification.
2. Background Art
In the past few years, digital pen devices have become very popular. People are increasingly using digital pens in a variety of applications including word processors, presentation software, calendaring and database programs, electronic mail including instant messenger, and so on. There are also a variety of devices that use pens as their main input devices such as cellular phones, Personal Data Assistants (PDAs), Pocket Personal Computers (PC), and Tablet PCs. For instance, Tablet PCs allow users to input data with a digital pen as well as a standard keyboard or mouse. Tablet PCs have special screens which use an active digitizer to enable users to write directly on the screen to control their PC and to input information as handwriting or a drawing. This process—called inking—enables users to add “digital ink” to a full range of applications, which appears as natural-looking handwriting on the screen. The digitized handwriting can be converted to standard text through handwriting recognition, or it can remain as handwritten text. Both the converted text in typeface and the cursive handwritten text function equally well as data formats in various applications and on various platforms. That is, both forms of text can be sent as e-mail from an email program and exchanged as documents in a word processor, and can be sent from the Tablet PC to a desktop computer or a Pocket PC, which can display the text in the same character format that it was sent in.
Compared to the keyboard device, one disadvantage with digital pen devices is the number of bits that are needed to represent the ink stokes. It only takes one byte of data to represent each ASCII letter when using a keyboard. However, when a letter is written with a digital pen or similar device, all the points in the stroke must be stored. At an average writing speed, the stroke of a letter contains on average about 50 points. Each point consists of two coordinates. In the most naïve way, it can be thought that 16 bits per coordinate are required. Therefore, a letter written by a digital pen device would typically need 2*16*50 or 1600 bits to store. A perhaps even more serious problem with the stroke representation of a digital pen is the bandwidth overhead in communication, especially since digital ink is so readily transferable between a variety of devices and applications. When people use pens to send an email or instant message, the amount of bandwidth required for the ink strokes is much larger than that required to transfer the ASCII letters generated by a keyboard for a similar amount of text created.
To address these problems, people have developed ink compression software. The emerging systems in this area of endeavor entropy encode the differences between the neighboring points of the stroke. Entropy encoding is a coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. Typically, entropy encoders are used to compress data by replacing symbols represented by equal-length codes with symbols represented by codes proportional to the negative logarithm of the probability. Therefore, the most common symbols use the shortest codes. Two of the most common entropy encoding techniques are Huffman coding and arithmetic coding. Since entropy encoding is lossless, however, the amount of compression that can be achieved for these emerging systems is limited.